W4. Complete and Incomplete FSAs, Operations on FSAs (Complement, Intersection, Union, Difference), Finite State Transducers, Regular Languages, Closure Properties

1. Summary

1.1 Representations of Finite State Automata

In previous lectures, we learned the formal definition of a Finite State Automaton (FSA). Now we explore two important variations in how the transition function can be defined: complete and incomplete FSAs.

1.1.1 Complete FSAs

A complete FSA is one where the transition function \(\delta\) is total, meaning it is defined for every possible combination of state and input symbol. Formally, for a complete FSA \(M = (Q, \Sigma, \delta, q_0, F)\), the transition function \(\delta: Q \times \Sigma \to Q\) must satisfy:

\[\forall q \in Q, \forall \sigma \in \Sigma: \delta(q, \sigma) \text{ is defined}\]

This means that no matter what state the automaton is in and what symbol it reads, there is always a defined transition to some state (which could be the same state via a self-loop).

Why is completeness important? A complete FSA guarantees that every string over the alphabet can be processed without getting “stuck.” The automaton will always have a well-defined final state, which is either accepting or rejecting.

Example: Consider an FSA over alphabet \(\{0, 1\}\) with two states \(q_0\) (accepting) and \(q_1\) (non-accepting):

• From \(q_0\): on input 0 → stay in \(q_0\), on input 1 → go to \(q_1\)
• From \(q_1\): on input 0 → go to \(q_0\), on input 1 → stay in \(q_1\)

This is complete because every combination \((q, \sigma)\) has a defined transition.

1.1.2 Incomplete FSAs

An incomplete FSA (also called a partial FSA) is one where the transition function \(\delta\) is partial, meaning some combinations of state and input symbol have no defined transition. Formally:

\[\exists q \in Q, \exists \sigma \in \Sigma: \delta(q, \sigma) \text{ is undefined}\]

What happens when we reach an undefined transition? When processing a string, if the FSA encounters a situation where \(\delta(q, \sigma)\) is undefined, the string is automatically rejected—the automaton cannot continue processing and therefore cannot reach an accepting state.

Example: Consider an FSA over alphabet \(\{a, b\}\):

• \(q_0\) (start) → on ‘a’ go to \(q_1\); on ‘b’ undefined
• \(q_1\) (accept) → on ‘b’ stay in \(q_1\); on ‘a’ undefined

This FSA accepts strings matching the pattern “a” followed by zero or more ‘b’s (\(\{ab^k : k \geq 0\}\)). Any string starting with ’b’ or containing ‘a’ after the first position will hit an undefined transition and be rejected.

Graphical Representation: In state diagrams, incomplete FSAs simply omit arrows for undefined transitions. Complete FSAs show all possible transitions.

1.1.3 Converting Incomplete FSAs to Complete FSAs

Any incomplete FSA can be converted to an equivalent complete FSA by adding a trap state (also called an error state or sink state). The process is:

1. Add a new non-accepting state \(q_{\text{trap}}\) (or \(q_E\) for “error”)
2. For every undefined transition \(\delta(q, \sigma)\), define it to go to the trap state: \(\delta(q, \sigma) = q_{\text{trap}}\)
3. Add self-loops on the trap state for all symbols: \(\delta(q_{\text{trap}}, \sigma) = q_{\text{trap}}\) for all \(\sigma \in \Sigma\)

The trap state has a special property: once entered, the automaton can never leave. Since it’s non-accepting, any string that leads to it will be rejected.

Example: Converting the incomplete FSA from above:

• Add \(q_{\text{trap}}\) (non-accepting)
• \(q_0\) on ‘b’ → \(q_{\text{trap}}\)
• \(q_1\) on ‘a’ → \(q_{\text{trap}}\)
• \(q_{\text{trap}}\) on ‘a’ → \(q_{\text{trap}}\)
• \(q_{\text{trap}}\) on ‘b’ → \(q_{\text{trap}}\)

Now every state-symbol combination has a defined transition, making the FSA complete while preserving the language it recognizes.

1.2 Regular Languages

A regular language is any language that can be recognized (accepted) by a finite state automaton. This is a fundamental concept in theoretical computer science.

Formal Definition: A language \(L \subseteq \Sigma^*\) is called regular if and only if there exists a finite state automaton \(M = (Q, \Sigma, \delta, q_0, F)\) such that \(L = L(M)\), where:

\[L(M) = \{w \in \Sigma^* : \delta^*(q_0, w) \in F\}\]

Here, \(L\) consists of exactly those strings that, when processed by \(M\), lead to an accepting state.

Important Properties of Regular Languages:

1. Decidability: For any regular language \(L\) and any string \(w\), we can algorithmically determine whether \(w \in L\) by simulating the FSA
2. Finiteness of description: Regular languages can be described by FSAs with finitely many states
3. Closure properties: Regular languages are closed under many operations (union, intersection, complement, concatenation, Kleene star)

Examples of Regular Languages:

• \(L_1 = \{w \in \{0,1\}^* : w \text{ contains an even number of 1's}\}\) (regular)
• \(L_2 = \{w \in \{a,b\}^* : w \text{ starts with } a\}\) (regular)
• \(L_3 = \{a^n b^n : n \geq 0\}\) (NOT regular—requires counting, which FSAs cannot do)

1.3 Operations on Finite State Automata

One of the most powerful properties of regular languages is that they are closed under various operations. This means that if we apply these operations to regular languages, the result is still a regular language. We can construct FSAs for the resulting languages using systematic methods.

1.3.1 Complement

Problem: Given an FSA \(M = (Q, \Sigma, \delta, q_0, F)\) that accepts language \(L\), construct an FSA that accepts the complement \(L^c = \Sigma^* \setminus L\) (all strings NOT in \(L\)).

Key Idea: To accept the opposite language, we “flip” the accepting and non-accepting states. A string previously accepted should now be rejected, and vice versa.

Construction for Complete FSAs:

Given a complete FSA \(M = (Q, \Sigma, \delta, q_0, F)\), the complement automaton is:

\[M^c = (Q, \Sigma, \delta, q_0, F^c)\]

where \(F^c = Q \setminus F\) (the set of states that were NOT accepting in \(M\)).

Everything stays the same except the accepting states are flipped.

Example: Consider an FSA over \(\{a\}\) with states \(q_0, q_1\):

• \(M\): \(q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_0\), with \(F = \{q_1\}\) (accepts strings with odd length)
• \(M^c\): Same transitions, but \(F^c = \{q_0\}\) (accepts strings with even length, including \(\epsilon\))

Why Does This Work? In a complete FSA, every string leads to some final state. If that state was accepting in \(M\), we want to reject it in \(M^c\), so we make it non-accepting. If it was non-accepting in \(M\), we want to accept it in \(M^c\), so we make it accepting.

Critical Requirement: Completeness

The simple “flip accepting states” approach only works for complete FSAs. Why?

In an incomplete FSA, some strings cause undefined transitions and are implicitly rejected (they don’t reach any state). When we flip accepting states, we’re only changing what happens to strings that DO complete processing. We’re not addressing strings that were rejected due to undefined transitions.

Construction for Incomplete FSAs:

To construct the complement of an incomplete FSA:

1. First, make the FSA complete by adding a trap state for all undefined transitions
2. Then, flip the accepting states: \(F^c = Q \setminus F\)

Example: Incomplete FSA: \(q_0 \xrightarrow{a} q_1\) (accepting), with \(q_1 \xrightarrow{b} q_1\) over alphabet \(\{a, b\}\).

Step 1: Add trap state \(q_2\). Define:

• \(q_0\) on ‘b’ → \(q_2\)
• \(q_1\) on ‘a’ → \(q_2\)
• \(q_2\) on ‘a’, ‘b’ → \(q_2\)

Step 2: Flip accepting states. Original \(F = \{q_1\}\), so \(F^c = \{q_0, q_2\}\).

The complement FSA accepts all strings except those starting with ‘a’ and continuing with only ’b’s.

1.3.2 Intersection

Problem: Given two FSAs \(M_1\) and \(M_2\) accepting languages \(L_1\) and \(L_2\) respectively, construct an FSA accepting \(L_1 \cap L_2\) (strings in BOTH languages).

Key Idea: We run both FSAs in parallel on the same input. We accept a string only if it would be accepted by BOTH individual FSAs.

Construction (Product Construction):

Given:

• \(M_1 = (Q_1, \Sigma, \delta_1, q_0^1, F_1)\)
• \(M_2 = (Q_2, \Sigma, \delta_2, q_0^2, F_2)\)

The intersection automaton is:

\[M_1 \cap M_2 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = Q_1 \times Q_2\) (Cartesian product: pairs of states)
• \(q_0 = (q_0^1, q_0^2)\) (pair of initial states)
• \(\delta((q, p), a) = (\delta_1(q, a), \delta_2(p, a))\) (transition in both simultaneously)
• \(F = \{(q, p) \in Q_1 \times Q_2 : q \in F_1 \land p \in F_2\}\) (BOTH must be accepting)

Intuition: Each state \((q, p)\) represents “\(M_1\) is in state \(q\) AND \(M_2\) is in state \(p\).” When we read a symbol, we update both components. We accept only when both components are in their respective accepting states.

Example:

\(M_1\) accepts strings with odd number of symbols (over \(\{a\}\)):

• States: \(q_0, q_1\)
• Transitions: \(q_0 \xrightarrow{a} q_1\), \(q_1 \xrightarrow{a} q_0\)
• Accepting: \(F_1 = \{q_1\}\)

\(M_2\) accepts all strings (over \(\{a\}\)):

• States: \(p_0\)
• Transitions: \(p_0 \xrightarrow{a} p_0\)
• Accepting: \(F_2 = \{p_0\}\)

Product automaton \(M_1 \cap M_2\):

• States: \((q_0, p_0), (q_1, p_0)\)
• Transitions: \((q_0, p_0) \xrightarrow{a} (q_1, p_0)\), \((q_1, p_0) \xrightarrow{a} (q_0, p_0)\)
• Accepting: \(F = \{(q_1, p_0)\}\) (where \(q_1 \in F_1\) and \(p_0 \in F_2\))

This accepts strings with odd number of symbols (same as \(M_1\), since \(M_2\) accepts everything).

Size: If \(|Q_1| = n\) and \(|Q_2| = m\), the product automaton has \(n \times m\) states. Not all may be reachable from the initial state, so we can often simplify by removing unreachable states.

1.3.3 Union

Problem: Given two FSAs \(M_1\) and \(M_2\) accepting languages \(L_1\) and \(L_2\), construct an FSA accepting \(L_1 \cup L_2\) (strings in EITHER language).

Construction:

The construction is almost identical to intersection, except for the accepting states:

\[M_1 \cup M_2 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = Q_1 \times Q_2\)
• \(q_0 = (q_0^1, q_0^2)\)
• \(\delta((q, p), a) = (\delta_1(q, a), \delta_2(p, a))\)
• \(F = \{(q, p) \in Q_1 \times Q_2 : q \in F_1 \lor p \in F_2\}\) (EITHER can be accepting)

The only difference from intersection is the accepting condition: We use logical OR (\(\lor\)) instead of AND (\(\land\)).

Example: Using the same \(M_1\) and \(M_2\) from the intersection example:

• Accepting states: \(F = \{(q_0, p_0), (q_1, p_0)\}\) (since \(p_0 \in F_2\), both states qualify)
• The initial state \((q_0, p_0)\) is accepting, so even \(\epsilon\) is accepted
• This accepts all strings (same as \(M_2\))

Alternative Construction Using De Morgan’s Laws:

We can also construct union using complement and intersection:

\[L_1 \cup L_2 = \overline{\overline{L_1} \cap \overline{L_2}}\]

This means: “NOT (NOT \(L_1\) AND NOT \(L_2\))” = “anything not excluded by both” = “accepted by at least one.”

1.3.4 Difference

Problem: Given two FSAs \(M_1\) and \(M_2\) accepting languages \(L_1\) and \(L_2\), construct an FSA accepting \(L_1 \setminus L_2\) (strings in \(L_1\) but NOT in \(L_2\)).

Construction:

Again using the product construction:

\[M_1 \setminus M_2 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = Q_1 \times Q_2\)
• \(q_0 = (q_0^1, q_0^2)\)
• \(\delta((q, p), a) = (\delta_1(q, a), \delta_2(p, a))\)
• \(F = \{(q, p) \in Q_1 \times Q_2 : q \in F_1 \land p \notin F_2\}\) (in \(F_1\) AND not in \(F_2\))

Intuition: We accept only when “\(M_1\) accepts” AND “\(M_2\) rejects.”

Example:

\(M_1\) accepts odd-length strings, \(M_2\) accepts all strings (from before).

• \(L_1 \setminus L_2 = \emptyset\) (nothing is in \(L_1\) but not in \(L_2\), since \(L_2\) is everything)
• Accepting: \(F = \emptyset\) (no state \((q, p)\) satisfies \(p \notin F_2\), since \(F_2 = \{p_0\}\) and all reachable states have \(p = p_0\))

Reversed Example: \(M_2 \setminus M_1\) (all strings except odd-length):

• Accepting: \(F = \{(q_0, p_0)\}\) (where \(p_0 \in F_2\) and \(q_0 \notin F_1\))
• This accepts even-length strings (including \(\epsilon\))

1.4 Finite State Transducers

A Finite State Transducer (FST) extends the concept of a finite state automaton by adding an output capability. While an FSA only accepts or rejects strings, an FST transforms input strings into output strings.

1.4.1 Formal Definition

A Finite State Transducer is a tuple:

\[T = (Q, I, \delta, q_0, F, O, \eta)\]

where:

• \((Q, I, \delta, q_0, F)\) is a standard FSA (the “acceptance” component)
• \(O\) is the output alphabet (a finite set of symbols for output)
• \(\eta: Q \times I \to O^*\) is the output function that maps each transition to a string of output symbols (possibly empty)

Key Points:

1. Translation is performed only on accepted strings: If the input string is not accepted by the underlying FSA, no output is produced (or the transducer fails)
2. Each transition can produce output: When transitioning from state \(q\) on input \(\sigma\), the transducer outputs \(\eta(q, \sigma)\)
3. Output can be empty (\(\epsilon\)): Some transitions produce no output

Graphical Representation: In diagrams, transitions are labeled as \(i/o\) where \(i\) is the input symbol and \(o\) is the output string.

1.4.2 Example: Removing Odd Occurrences of 0 and Doubling 1s

Problem: Build an FST over alphabet \(A = \{0, 1\}\) that:

• Accepts strings with an even number of 0’s
• Outputs a transformed string where:
  • Every odd occurrence of 0 is removed (outputs \(\epsilon\))
  • Every even occurrence of 0 is kept (outputs 0)
  • Every 1 is doubled (outputs 11)

Examples:

• Input: “010010” → Output: “110110”
  • 0 (1st, odd) → \(\epsilon\)
  • 1 → 11
  • 0 (2nd, even) → 0
  • 0 (3rd, odd) → \(\epsilon\)
  • 1 → 11
  • 0 (4th, even) → 0
• Input: “00” → Output: “0”
  • 0 (1st, odd) → \(\epsilon\)
  • 0 (2nd, even) → 0
• Input: “000100011” → Output: “011001111”
  • 0 (odd) → \(\epsilon\), 0 (even) → 0, 0 (odd) → \(\epsilon\), 1 → 11, 0 (even) → 0, 0 (odd) → \(\epsilon\), 0 (even) → 0, 1 → 11, 1 → 11

FST Construction:

• States:
  • \(q_0\) (accepting): “Seen an even number of 0’s”
  • \(q_1\): “Seen an odd number of 0’s”
• Transitions and Outputs:
  • \(q_0 \xrightarrow{1/11} q_0\) (loop: reading 1, output 11, stay in even state)
  • \(q_0 \xrightarrow{0/\epsilon} q_1\) (reading 1st/3rd/… 0, output nothing, go to odd state)
  • \(q_1 \xrightarrow{1/11} q_1\) (loop: reading 1, output 11, stay in odd state)
  • \(q_1 \xrightarrow{0/0} q_0\) (reading 2nd/4th/… 0, output 0, return to even state)
• Accepting states: \(F = \{q_0\}\) (even number of 0’s)

How it works: The transducer tracks parity (even/odd count) of 0’s using states. Each transition specifies what to output. For 1’s, output is always “11”. For 0’s, output depends on whether it’s an odd occurrence (\(\epsilon\)) or even occurrence (0).

1.4.3 Applications of FSTs

FSTs are used in many practical applications:

• Text processing: Find-and-replace operations, spell correction
• Natural language processing: Morphological analysis (e.g., converting “walked” to “walk”)
• Compilers: Translating source code patterns to target code
• Data compression: Encoding/decoding schemes
• Regular expression replacement: Implementing operations like s/pattern/replacement/g

1.5 Closure Properties of Regular Languages

A family of languages \(\mathcal{L}\) is closed under an operation OP if: whenever languages \(L_1, L_2 \in \mathcal{L}\), the result \(L_1 \text{ OP } L_2\) is also in \(\mathcal{L}\).

What does closure mean intuitively? Think of a set being “closed” like a closed system in physics—no matter what operations you perform inside the system, you never leave it. For languages, if you start with regular languages and apply certain operations, you get back regular languages.

Regular languages are closed under:

1. Union: \(L_1 \cup L_2\) is regular (proven by product construction)
2. Intersection: \(L_1 \cap L_2\) is regular (proven by product construction)
3. Complement: \(\overline{L}\) is regular (proven by flipping accepting states in complete FSA)
4. Difference: \(L_1 \setminus L_2\) is regular (proven by product construction)
5. Concatenation: \(L_1 \cdot L_2 = \{xy : x \in L_1, y \in L_2\}\) is regular
6. Kleene star: \(L^* = \bigcup_{k=0}^{\infty} L^k\) is regular

Why is closure important?

1. Compositional reasoning: We can build complex regular languages from simpler ones
2. Proving regularity: If we know \(L_1\) and \(L_2\) are regular, we immediately know \(L_1 \cup L_2\) is regular without constructing an FSA
3. Compiler design: Combining patterns to recognize complex tokens

Example: The language \(L = \{w \in \{0,1\}^* : w \text{ has even 0's or odd 1's}\}\) is regular because:

• \(L_1 = \{w : w \text{ has even 0's}\}\) is regular
• \(L_2 = \{w : w \text{ has odd 1's}\}\) is regular
• \(L = L_1 \cup L_2\) is regular (by closure under union)

1.6 Practical Considerations: Simplifying FSAs

When constructing FSAs using operations like intersection or union, the resulting automaton may have unreachable states—states that cannot be reached from the initial state. These can be removed without changing the language.

Example: In the product construction, if \(|Q_1| = 3\) and \(|Q_2| = 4\), the product has \(3 \times 4 = 12\) states. But not all combinations \((q, p)\) may be reachable from the initial state \((q_0^1, q_0^2)\).

Simplification algorithm:

1. Mark the initial state as reachable
2. Iteratively mark states reachable from already-marked states via any transition
3. Remove all unmarked states and their transitions

This process is important for practical implementation, as it reduces the size and complexity of the automaton.

---

2. Definitions

• Complete FSA: A finite state automaton where the transition function \(\delta: Q \times \Sigma \to Q\) is total, meaning \(\delta(q, \sigma)\) is defined for every state \(q \in Q\) and every symbol \(\sigma \in \Sigma\).
• Incomplete FSA (Partial FSA): A finite state automaton where the transition function is partial, meaning some combinations of state and input symbol have no defined transition. Strings reaching undefined transitions are automatically rejected.
• Trap State (Error State, Sink State): A non-accepting state added to an incomplete FSA to make it complete. All undefined transitions lead to the trap state, which has self-loops for all input symbols, ensuring that once entered, the automaton remains there and rejects the string.
• Regular Language: A language \(L \subseteq \Sigma^*\) that can be recognized (accepted) by some finite state automaton. Equivalently, \(L\) is regular if there exists an FSA \(M\) such that \(L = L(M)\).
• Complement of a Language: For a language \(L\) over alphabet \(\Sigma\), the complement \(L^c\) (or \(\overline{L}\)) is the set of all strings over \(\Sigma\) that are not in \(L\): \(L^c = \Sigma^* \setminus L\).
• Intersection of Languages: For languages \(L_1\) and \(L_2\) over the same alphabet, the intersection \(L_1 \cap L_2\) is the set of strings that belong to both languages: \(L_1 \cap L_2 = \{w \in \Sigma^* : w \in L_1 \land w \in L_2\}\).
• Union of Languages: For languages \(L_1\) and \(L_2\), the union \(L_1 \cup L_2\) is the set of strings that belong to at least one of the languages: \(L_1 \cup L_2 = \{w \in \Sigma^* : w \in L_1 \lor w \in L_2\}\).
• Difference of Languages: For languages \(L_1\) and \(L_2\), the difference \(L_1 \setminus L_2\) is the set of strings in \(L_1\) but not in \(L_2\): \(L_1 \setminus L_2 = \{w \in \Sigma^* : w \in L_1 \land w \notin L_2\}\).
• Product Construction: A method for combining two FSAs \(M_1\) and \(M_2\) into a single FSA whose states are pairs \((q, p)\) where \(q \in Q_1\) and \(p \in Q_2\). The construction simulates running both automata in parallel on the same input.
• Cartesian Product of Sets: For sets \(A\) and \(B\), the Cartesian product \(A \times B = \{(a, b) : a \in A, b \in B\}\) is the set of all ordered pairs.
• Finite State Transducer (FST): An extension of a finite state automaton that produces output strings in addition to accepting or rejecting input. Formally defined as \(T = (Q, I, \delta, q_0, F, O, \eta)\) where \(O\) is the output alphabet and \(\eta: Q \times I \to O^*\) is the output function.
• Output Function (\(\eta\)): In an FST, the function \(\eta: Q \times I \to O^*\) that specifies what output string (possibly empty) is produced when transitioning from a state on a given input symbol.
• Closure Property: A family of languages \(\mathcal{L}\) is closed under an operation if applying that operation to languages in \(\mathcal{L}\) produces another language in \(\mathcal{L}\). Regular languages are closed under union, intersection, complement, difference, concatenation, and Kleene star.
• Unreachable State: A state in an FSA that cannot be reached from the initial state by any sequence of transitions. Unreachable states can be removed without changing the language accepted by the FSA.

---

3. Formulas

• Complement FSA (Complete): For a complete FSA \(M = (Q, \Sigma, \delta, q_0, F)\), the complement is \(M^c = (Q, \Sigma, \delta, q_0, F^c)\) where \(F^c = Q \setminus F\)
• Intersection FSA (Product Construction): For \(M_1 = (Q_1, \Sigma, \delta_1, q_0^1, F_1)\) and \(M_2 = (Q_2, \Sigma, \delta_2, q_0^2, F_2)\), the intersection is \(M_1 \cap M_2 = (Q, \Sigma, \delta, q_0, F)\) where:
  • \(Q = Q_1 \times Q_2\)
  • \(q_0 = (q_0^1, q_0^2)\)
  • \(\delta((q, p), a) = (\delta_1(q, a), \delta_2(p, a))\)
  • \(F = \{(q, p) \in Q_1 \times Q_2 : q \in F_1 \land p \in F_2\}\)
• Union FSA (Product Construction): Same as intersection except \(F = \{(q, p) \in Q_1 \times Q_2 : q \in F_1 \lor p \in F_2\}\)
• Difference FSA (Product Construction): Same as intersection except \(F = \{(q, p) \in Q_1 \times Q_2 : q \in F_1 \land p \notin F_2\}\)
• De Morgan’s Laws for Languages: \(L_1 \cup L_2 = \overline{\overline{L_1} \cap \overline{L_2}}\) and \(L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}\)

---

4. Examples

4.1. Constructing an FST: Past Tense to Present Tense (Lab 4, Task 1)

Build a complete FST over alphabet \(A = \{w, t, a, l, k, e, d\}\) that:

• Accepts only the verbs “walked” or “talked”
• Translates the input verb to present tense (removes the “ed”)

Click to see the solution

Key Concept: The FST reads the input character by character, outputting the appropriate transformation. For “walked” → “walk”, we output each letter except the final “ed”.

FST mapping walked/talked to walk/talk

1. Design the states:
   • \(q_0\) (start): Haven’t seen anything yet
   • \(q_1\): Seen “w” or “t”
   • \(q_2\): Seen “wa” or “ta”
   • \(q_3\): Seen “wal” or “tal”
   • \(q_4\): Seen “walk” or “talk”
   • \(q_5\): Seen “walke” or “talke”
   • \(q_6\) (accepting): Seen complete “walked” or “talked”
   • \(q_{\text{trap}}\): Error state for invalid inputs
2. Define transitions and outputs:
   • From \(q_0\): on ‘w’ output ‘w’, go to \(q_1\); on ‘t’ output ‘t’, go to \(q_1\); else go to trap
   • From \(q_1\): on ‘a’ output ‘a’, go to \(q_2\); else go to trap
   • From \(q_2\): on ‘l’ output ‘l’, go to \(q_3\); else go to trap
   • From \(q_3\): on ‘k’ output ‘k’, go to \(q_4\); else go to trap
   • From \(q_4\): on ‘e’ output \(\epsilon\), go to \(q_5\) (don’t output ‘e’)
   • From \(q_5\): on ‘d’ output \(\epsilon\), go to \(q_6\) (don’t output ‘d’)
   • \(q_6\) is accepting
   • Trap state loops with no output

Verification:

• Input: “walked” → Output: “w” + “a” + “l” + “k” + \(\epsilon\) + \(\epsilon\) = “walk” ✓
• Input: “talked” → Output: “t” + “a” + “l” + “k” + \(\epsilon\) + \(\epsilon\) = “talk” ✓

Answer: The FST has states \(q_0\) through \(q_6\) with transitions as described, outputting each character except ‘e’ and ‘d’ at the end.

4.2. Constructing an FST: Erasing Every Second ‘a’ (Lab 4, Task 2)

Build a complete FST over alphabet \(A = \{a, b\}\) that:

• Accepts only strings ending with the letter ‘b’
• Translates the input by erasing every second occurrence of ‘a’

Click to see the solution

Key Concept: Track the parity of ‘a’s seen so far. Output ’a’ on odd occurrences, erase (output \(\epsilon\)) on even occurrences. Always output ‘b’.

FST erasing every second a while requiring the string to end in b

1. Design states:
   • \(q_0\) (start): Seen even number of ‘a’s, not ended with ’b’
   • \(q_1\): Seen odd number of ‘a’s, not ended with ’b’
   • \(q_2\) (accepting): Seen even number of ‘a’s, ended with ’b’
   • \(q_3\) (accepting): Seen odd number of ‘a’s, ended with ’b’
2. Transitions and outputs:
   • From \(q_0\): on ‘a’ output ‘a’, go to \(q_1\) (first ‘a’, odd count); on ‘b’ output ‘b’, go to \(q_2\)
   • From \(q_1\): on ‘a’ output \(\epsilon\), go to \(q_0\) (second ‘a’, even count, erase); on ‘b’ output ‘b’, go to \(q_3\)
   • From \(q_2\): on ‘a’ output ‘a’, go to \(q_3\); on ‘b’ output ‘b’, stay in \(q_2\)
   • From \(q_3\): on ‘a’ output \(\epsilon\), go to \(q_2\); on ‘b’ output ‘b’, stay in \(q_3\)
3. Accepting states: \(F = \{q_2, q_3\}\) (ended with ‘b’)

Verification:

• Input: “aaab” → Outputs: ‘a’ (1st ‘a’), \(\epsilon\) (2nd ‘a’), ‘a’ (3rd ‘a’), ‘b’ → “aab” ✓
• Input: “aabb” → Outputs: ‘a’, \(\epsilon\), ‘b’, ‘b’ → “abb” ✓

Answer: The FST has four states tracking parity of ‘a’s and whether the string ends with ’b’, with outputs as described.

4.3. Building FSAs for Even 1’s and Odd 0’s (Lab 4, Task 3)

Let \(A = \{0, 1\}\) be the alphabet.

Problem 1: Build a complete FSA \(M_1\) that recognizes: \[L_1 = \{x \in A^* : x \text{ has an even number of 1's}\}\]

Problem 2: Build a complete FSA \(M_2\) that recognizes: \[L_2 = \{x \in A^* : x \text{ has an odd number of 0's}\}\]

Click to see the solution

Key Concept: Track parity (even/odd count) using two states. Reading the tracked symbol toggles the state.

Two parity FSAs: even number of 1s and odd number of 0s

(a) FSA for Even Number of 1’s (\(M_1\)):

1. States:
   • \(q_0\) (start, accepting): Even number of 1’s seen
   • \(q_1\): Odd number of 1’s seen
2. Transitions:
   • From \(q_0\): on ‘0’ stay in \(q_0\) (0’s don’t affect count); on ‘1’ go to \(q_1\) (even → odd)
   • From \(q_1\): on ‘0’ stay in \(q_1\); on ‘1’ go to \(q_0\) (odd → even)
3. Accepting: \(F = \{q_0\}\)

Verification:

• ““: in \(q_0\) → ACCEPT (zero 1’s is even) ✓
• “11”: \(q_0 \xrightarrow{1} q_1 \xrightarrow{1} q_0\) → ACCEPT ✓
• “101”: \(q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_1 \xrightarrow{1} q_0\) → ACCEPT ✓
• “1”: \(q_0 \xrightarrow{1} q_1\) → REJECT ✓

(b) FSA for Odd Number of 0’s (\(M_2\)):

1. States:
   • \(p_0\) (start): Even number of 0’s seen
   • \(p_1\) (accepting): Odd number of 0’s seen
2. Transitions:
   • From \(p_0\): on ‘1’ stay in \(p_0\); on ‘0’ go to \(p_1\) (even → odd)
   • From \(p_1\): on ‘1’ stay in \(p_1\); on ‘0’ go to \(p_0\) (odd → even)
3. Accepting: \(F = \{p_1\}\)

Answer:

• \(M_1\) has states \(\{q_0, q_1\}\) with \(q_0\) accepting
• \(M_2\) has states \(\{p_0, p_1\}\) with \(p_1\) accepting

4.4. Combining FSAs: Union, Intersection, Difference (Lab 4, Task 4)

Using the FSAs \(M_1\) and \(M_2\) from Example 4.11:

Problem 3: Build a complete FSA that accepts when EITHER \(M_1\) OR \(M_2\) accepts (union).

Problem 4: Build a complete FSA that accepts when BOTH \(M_1\) AND \(M_2\) accept (intersection).

Problem 5: Build a complete FSA that accepts when \(M_1\) accepts AND \(M_2\) rejects (difference).

Problem 6: Build a complement for \(M_1\).

Click to see the solution

Key Concept: Use product construction for all except complement. Accepting states differ based on the operation.

Product construction viewpoint for union, intersection, and difference

(Problem 3) Union: \(M_1 \cup M_2\)

1. Product construction:
   • \(Q = \{q_0, q_1\} \times \{p_0, p_1\} = \{(q_0, p_0), (q_0, p_1), (q_1, p_0), (q_1, p_1)\}\)
   • Initial: \((q_0, p_0)\)
   • Transitions: \(\delta((q, p), \sigma) = (\delta_1(q, \sigma), \delta_2(p, \sigma))\)
2. Accepting states (at least one component accepting): \(F = \{(q, p) : q \in \{q_0\} \lor p \in \{p_1\}\}\) \(F = \{(q_0, p_0), (q_0, p_1), (q_1, p_1)\}\)

Answer: The union FSA has 4 states with 3 accepting states: \((q_0, p_0), (q_0, p_1), (q_1, p_1)\).

(Problem 4) Intersection: \(M_1 \cap M_2\)

1. Same product construction
2. Accepting states (both components accepting): \(F = \{(q, p) : q \in \{q_0\} \land p \in \{p_1\}\}\) \(F = \{(q_0, p_1)\}\)

Answer: The intersection FSA has 4 states with 1 accepting state: \((q_0, p_1)\).

(Problem 5) Difference: \(M_1 \setminus M_2\)

1. Same product construction
2. Accepting states (\(M_1\) accepts, \(M_2\) rejects): \(F = \{(q, p) : q \in \{q_0\} \land p \notin \{p_1\}\}\) \(F = \{(q, p) : q = q_0 \land p = p_0\}\) \(F = \{(q_0, p_0)\}\)

Answer: The difference FSA has 4 states with 1 accepting state: \((q_0, p_0)\).

(Problem 6) Complement: \(M_1^c\)

1. \(M_1\) is already complete (has transitions for all inputs)
2. Flip accepting states: Original \(F = \{q_0\}\) Complement \(F^c = \{q_0, q_1\} \setminus \{q_0\} = \{q_1\}\)

Answer: \(M_1^c\) has the same states and transitions as \(M_1\), but with \(F = \{q_1\}\) (accepts odd number of 1’s).

4.5. Complement of Incomplete FSA (Lab 4, Task 5)

Construct a complement for the following incomplete FSA over alphabet \(\{0, 1\}\):

• \(q_0\) (start, accepting): loops on ‘1’; goes to \(q_1\) on ‘0’
• \(q_1\): goes to \(q_0\) on ‘0’; transition on ‘1’ is undefined

Click to see the solution

Key Concept: First complete the FSA, then flip accepting states.

Completing an incomplete FSA with a trap state before taking the complement

1. Add trap state \(q_2\) for undefined transitions:
   • \(q_1\) on ‘1’ → \(q_2\)
   • \(q_2\) on ‘0’ → \(q_2\)
   • \(q_2\) on ‘1’ → \(q_2\) (self-loops)
2. Complete FSA:
   • States: \(q_0\) (accepting), \(q_1, q_2\)
   • All transitions defined
3. Flip accepting states: Original \(F = \{q_0\}\) Complement \(F^c = \{q_1, q_2\}\)

Answer: The complement FSA has states \(\{q_0, q_1, q_2\}\) with accepting states \(F = \{q_1, q_2\}\).

4.6. FSAs for Divisibility by 2 and 3 (Lab 4, Task 6)

Let \(A = \{0, 1\}\) be the alphabet. Assume \(\epsilon\) is part of both languages.

Problem 1: Build a complete FSA \(M_a\) that recognizes: \[L_a = \{x \in A^* : x \text{ is the binary representation of an integer divisible by 2}\}\]

Problem 2: Build a complete FSA \(M_b\) that recognizes: \[L_b = \{x \in A^* : x \text{ is the binary representation of an integer divisible by 3}\}\]

Click to see the solution

Key Concept: Divisibility can be determined by examining specific patterns in binary representation.

FSAs for divisibility by 2 and divisibility by 3 in binary

(a) Divisibility by 2:

A binary number is divisible by 2 if and only if its last digit is 0 (or it’s the empty string, representing 0).

1. States:
   • \(q_0\) (start, accepting): Last digit seen is 0, or no digits yet (\(\epsilon\))
   • \(q_1\): Last digit seen is 1
2. Transitions:
   • From \(q_0\): on ‘0’ stay in \(q_0\) (last digit is 0); on ‘1’ go to \(q_1\) (last digit is 1)
   • From \(q_1\): on ‘0’ go to \(q_0\) (last digit is 0); on ‘1’ stay in \(q_1\) (last digit is 1)
3. Accepting: \(F = \{q_0\}\)

Verification:

• \(\epsilon\) → in \(q_0\) → ACCEPT (represents 0, divisible by 2) ✓
• “10” (= 2) → \(q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_0\) → ACCEPT ✓
• “11” (= 3) → \(q_0 \xrightarrow{1} q_1 \xrightarrow{1} q_1\) → REJECT ✓

(b) Divisibility by 3:

We track the remainder when the number is divided by 3. Reading binary digits left-to-right, we update the remainder using: \(\text{new\_remainder} = (2 \times \text{old\_remainder} + \text{digit}) \mod 3\).

1. States (represent remainder mod 3):

   • \(r_0\) (start, accepting): Remainder is 0 (divisible by 3)
   • \(r_1\): Remainder is 1
   • \(r_2\): Remainder is 2

2. Transitions: From state \(r_i\), reading digit \(d\):

   • New state: \(r_{(2i + d) \mod 3}\)

   Explicitly:

   • From \(r_0\): on ‘0’ → \(r_0\) (\((2 \cdot 0 + 0) \mod 3 = 0\)); on ‘1’ → \(r_1\) (\((2 \cdot 0 + 1) \mod 3 = 1\))
   • From \(r_1\): on ‘0’ → \(r_2\) (\((2 \cdot 1 + 0) \mod 3 = 2\)); on ‘1’ → \(r_0\) (\((2 \cdot 1 + 1) \mod 3 = 0\))
   • From \(r_2\): on ‘0’ → \(r_1\) (\((2 \cdot 2 + 0) \mod 3 = 1\)); on ‘1’ → \(r_2\) (\((2 \cdot 2 + 1) \mod 3 = 2\))

3. Accepting: \(F = \{r_0\}\)

Verification:

• \(\epsilon\) → in \(r_0\) → ACCEPT (0 divisible by 3) ✓
• “11” (= 3) → \(r_0 \xrightarrow{1} r_1 \xrightarrow{1} r_0\) → ACCEPT ✓
• “110” (= 6) → \(r_0 \xrightarrow{1} r_1 \xrightarrow{1} r_0 \xrightarrow{0} r_0\) → ACCEPT ✓
• “10” (= 2) → \(r_0 \xrightarrow{1} r_1 \xrightarrow{0} r_2\) → REJECT ✓

Answer:

• \(M_a\) has 2 states, accepting when last digit is 0
• \(M_b\) has 3 states, accepting when remainder mod 3 is 0

4.7. Combining Divisibility FSAs (Lab 4, Task 7)

Using \(M_a\) and \(M_b\) from Example 4.14:

Problem 3: Build a complete FSA that accepts when BOTH \(M_a\) and \(M_b\) accept (divisible by both 2 and 3, i.e., divisible by 6).

Problem 4: Build a complete FSA that accepts when EITHER \(M_a\) or \(M_b\) accepts (divisible by 2 or 3).

Problem 5: Build a complete FSA that accepts when \(M_a\) accepts and \(M_b\) rejects (divisible by 2 but not 3).

Click to see the solution

Key Concept: Use product construction with appropriate accepting conditions.

Product automaton for combining divisibility by 2 and divisibility by 3

(Problem 3) Divisible by 6: \(M_a \cap M_b\)

1. Product states: \(Q = \{q_0, q_1\} \times \{r_0, r_1, r_2\} = 6\) states Initial: \((q_0, r_0)\)
2. Accepting (divisible by both 2 and 3): \(F = \{(q, r) : q \in \{q_0\} \land r \in \{r_0\}\} = \{(q_0, r_0)\}\)

Answer: The FSA for divisibility by 6 has 6 states with 1 accepting state: \((q_0, r_0)\).

(Problem 4) Divisible by 2 or 3: \(M_a \cup M_b\)

1. Same product states
2. Accepting (divisible by 2 OR 3): \(F = \{(q, r) : q \in \{q_0\} \lor r \in \{r_0\}\}\) \(F = \{(q_0, r_0), (q_0, r_1), (q_0, r_2), (q_1, r_0)\}\)

Answer: The FSA has 6 states with 4 accepting states.

(Problem 5) Divisible by 2 but not 3: \(M_a \setminus M_b\)

1. Same product states
2. Accepting (divisible by 2 AND NOT by 3): \(F = \{(q, r) : q \in \{q_0\} \land r \notin \{r_0\}\}\) \(F = \{(q_0, r_1), (q_0, r_2)\}\)

Answer: The FSA has 6 states with 2 accepting states: \((q_0, r_1)\) and \((q_0, r_2)\).

4.8. Complex Product Construction (Lab 4, Task 8)

Let \(M_1\) and \(M_2\) be the complete FSAs depicted over alphabet \(\{a, b\}\):

\(M_1\):

• States: \(A\) (start), \(B\), \(C\) (accepting)
• Transitions: \(A\) loops on ‘b’, goes to \(B\) on ‘a’; \(B\) loops on ‘a’, goes to \(C\) on ‘b’; \(C\) goes to \(A\) on ‘b’

\(M_2\):

• States: \(X\) (start), \(Y\), \(Z\) (accepting)
• Transitions: \(X\) loops on ‘a’, goes to \(Y\) on ‘b’; \(Y\) goes to \(X\) on ‘a’, goes to \(Z\) on ‘b’; \(Z\) loops on ‘a’ and ‘b’

Draw complete FSAs accepting:

(i) \(L_1 \cup L_2\) (ii) \(L_1 \cap L_2\) (iii) \(L_1 \setminus L_2\)

Click to see the solution

Key Concept: Use product construction, then identify accepting states based on the operation.

(i) Union: \(L_1 \cup L_2\)

1. Product states: \(\{A, B, C\} \times \{X, Y, Z\} = 9\) states Initial: \((A, X)\)

2. Accepting states (at least one component accepting): \(F = \{(q, p) : q = C \lor p = Z\}\)

   Explicitly: \((C, X), (C, Y), (C, Z), (A, Z), (B, Z)\)

3. Transitions: Apply \(\delta((q, p), \sigma) = (\delta_1(q, \sigma), \delta_2(p, \sigma))\) for all states and symbols

Answer: 9-state FSA with 5 accepting states (all pairs where \(q = C\) or \(p = Z\)).

(ii) Intersection: \(L_1 \cap L_2\)

1. Same product construction
2. Accepting states (both components accepting): \(F = \{(q, p) : q = C \land p = Z\}\) \(F = \{(C, Z)\}\)

Answer: 9-state FSA with 1 accepting state: \((C, Z)\).

(iii) Difference: \(L_1 \setminus L_2\)

1. Same product construction
2. Accepting states (\(M_1\) accepts, \(M_2\) rejects): \(F = \{(q, p) : q = C \land p \neq Z\}\) \(F = \{(C, X), (C, Y)\}\)

Answer: 9-state FSA with 2 accepting states: \((C, X)\) and \((C, Y)\).

4.9. Converting State Diagram to State Table (Tutorial 4, Example 1)

Given an FSA as a State Transition Diagram, build a State Transition Table.

The FSA has three states: \(q_0\) (start), \(q_1\), and \(q_2\) (accepting), over alphabet \(\{a, b\}\). Transitions:

• \(q_0 \xrightarrow{a} q_0\), \(q_0 \xrightarrow{b} q_1\)
• \(q_1 \xrightarrow{b} q_0\), \(q_1 \xrightarrow{a} q_2\)
• \(q_2 \xrightarrow{a} q_2\), \(q_2 \xrightarrow{b} q_1\)

Click to see the solution

Key Concept: A state transition table is an alternative representation of an FSA, showing transitions in tabular form. Rows represent states, columns represent input symbols, and entries show the destination state.

1. Create the table structure:
   • Rows: One for each state (\(q_0, q_1, q_2\))
   • Columns: One for each symbol in the alphabet (\(a, b\))
   • Mark the initial state with \(\to\) and accepting states with \(*\)
2. Fill in transitions from the diagram:
   • From \(q_0\): on ‘a’ go to \(q_0\), on ‘b’ go to \(q_1\)
   • From \(q_1\): on ‘a’ go to \(q_2\), on ‘b’ go to \(q_0\)
   • From \(q_2\): on ‘a’ go to \(q_2\), on ‘b’ go to \(q_1\)

State Transition Table:

	a	b
\(\to q_0\)	\(q_0\)	\(q_1\)
\(q_1\)	\(q_2\)	\(q_0\)
\(*q_2\)	\(q_2\)	\(q_1\)

Answer: The completed state transition table is shown above.

4.10. Completing an Incomplete FSA (Tutorial 4, Example 2)

Given an incomplete FSA over alphabet \(\{a, b\}\):

• \(q_0\) (start) \(\xrightarrow{a} q_1\) (accepting)
• \(q_1\) (accepting) \(\xrightarrow{b} q_1\) (self-loop)

Transitions on ‘b’ from \(q_0\) and ‘a’ from \(q_1\) are undefined. Make this FSA complete.

Click to see the solution

Key Concept: To complete an FSA, add a trap state and define all missing transitions to lead to it.

1. Identify undefined transitions:
   • \(\delta(q_0, b)\) is undefined
   • \(\delta(q_1, a)\) is undefined
2. Add a trap state \(q_2\) (non-accepting)
3. Define the missing transitions to go to the trap:
   • \(q_0 \xrightarrow{b} q_2\)
   • \(q_1 \xrightarrow{a} q_2\)
4. Add self-loops on the trap state for all symbols:
   • \(q_2 \xrightarrow{a} q_2\)
   • \(q_2 \xrightarrow{b} q_2\)

Complete FSA:

• States: \(q_0\) (start), \(q_1\) (accepting), \(q_2\) (trap, non-accepting)
• Transitions:
  • \(q_0 \xrightarrow{a} q_1\), \(q_0 \xrightarrow{b} q_2\)
  • \(q_1 \xrightarrow{a} q_2\), \(q_1 \xrightarrow{b} q_1\)
  • \(q_2 \xrightarrow{a} q_2\), \(q_2 \xrightarrow{b} q_2\)

Answer: The completed FSA includes a trap state \(q_2\) with all previously undefined transitions leading to it.

4.11. Complement of a Complete FSA (Tutorial 4, Example 3)

Given a complete FSA \(M\) over alphabet \(\{a\}\):

• \(M = \langle \{q_0, q_1\}, \{a\}, \{((q_0, a), q_1), ((q_1, a), q_0)\}, q_0, \{q_1\} \rangle\)

This FSA accepts strings with an odd number of ’a’s. Construct \(M^c\), the complement.

Click to see the solution

Key Concept: For a complete FSA, the complement is obtained by flipping accepting and non-accepting states.

1. Identify the original accepting states: \(F = \{q_1\}\)
2. Compute the complement set: \(F^c = Q \setminus F = \{q_0, q_1\} \setminus \{q_1\} = \{q_0\}\)
3. Construct the complement FSA: \[M^c = \langle \{q_0, q_1\}, \{a\}, \{((q_0, a), q_1), ((q_1, a), q_0)\}, q_0, \{q_0\} \rangle\]

Everything is the same except \(F\) is replaced by \(F^c = \{q_0\}\).

Verification:

• Original \(M\) accepts: “a”, “aaa”, “aaaaa”, … (odd lengths)
• Complement \(M^c\) accepts: \(\epsilon\), “aa”, “aaaa”, … (even lengths, including zero)

Answer: \(M^c = \langle \{q_0, q_1\}, \{a\}, \{((q_0, a), q_1), ((q_1, a), q_0)\}, q_0, \{q_0\} \rangle\) which accepts strings with an even number of ’a’s.

4.12. Complement of an Incomplete FSA (Tutorial 4, Example 4)

Given an incomplete FSA over alphabet \(\{a, b\}\):

• \(q_0\) (start) \(\xrightarrow{a} q_1\) (accepting)
• \(q_1\) \(\xrightarrow{b} q_1\) (self-loop)

Construct the complement FSA.

Click to see the solution

Key Concept: For incomplete FSAs, we must first make them complete before computing the complement.

1. Make the FSA complete by adding a trap state:
   • Add state \(q_2\) (trap)
   • \(q_0 \xrightarrow{b} q_2\) (was undefined)
   • \(q_1 \xrightarrow{a} q_2\) (was undefined)
   • \(q_2 \xrightarrow{a} q_2\), \(q_2 \xrightarrow{b} q_2\) (self-loops)
2. The complete FSA has:
   • States: \(q_0, q_1, q_2\)
   • Accepting states: \(F = \{q_1\}\)
3. Compute the complement:
   • \(F^c = \{q_0, q_1, q_2\} \setminus \{q_1\} = \{q_0, q_2\}\)

Complement FSA:

• States: \(q_0\) (start, accepting), \(q_1\) (non-accepting), \(q_2\) (accepting)
• Same transitions as the completed version
• Accepting states: \(\{q_0, q_2\}\)

Answer: The complement FSA accepts all strings except those of the form \(ab^k\) for \(k \geq 0\).

4.13. Intersection of Two FSAs (Tutorial 4, Example 5)

Given:

• \(M_1 = \langle \{q_0, q_1\}, \{a\}, \delta_1, q_0, \{q_1\} \rangle\) where \(\delta_1(q_0, a) = q_1\), \(\delta_1(q_1, a) = q_0\) (accepts odd-length strings)
• \(M_2 = \langle \{p_0\}, \{a\}, \delta_2, p_0, \{p_0\} \rangle\) where \(\delta_2(p_0, a) = p_0\) (accepts all strings)

Construct \(M_1 \cap M_2\).

Click to see the solution

Key Concept: Use the product construction with accepting states being pairs where both components are accepting.

1. Determine the product states: \(Q = Q_1 \times Q_2 = \{q_0, q_1\} \times \{p_0\} = \{(q_0, p_0), (q_1, p_0)\}\)
2. Determine the initial state: \(q_0 = (q_0^1, q_0^2) = (q_0, p_0)\)
3. Define transitions using \(\delta((q, p), a) = (\delta_1(q, a), \delta_2(p, a))\):
   • \(\delta((q_0, p_0), a) = (\delta_1(q_0, a), \delta_2(p_0, a)) = (q_1, p_0)\)
   • \(\delta((q_1, p_0), a) = (\delta_1(q_1, a), \delta_2(p_0, a)) = (q_0, p_0)\)
4. Determine accepting states (both components must be accepting): \(F = \{(q, p) : q \in F_1 \land p \in F_2\} = \{(q, p) : q \in \{q_1\} \land p \in \{p_0\}\} = \{(q_1, p_0)\}\)

Product FSA:

\[M_1 \cap M_2 = \langle \{(q_0, p_0), (q_1, p_0)\}, \{a\}, \delta, (q_0, p_0), \{(q_1, p_0)\} \rangle\]

where:

• \(\delta((q_0, p_0), a) = (q_1, p_0)\)
• \(\delta((q_1, p_0), a) = (q_0, p_0)\)

Answer: The intersection FSA accepts strings with odd length (same as \(M_1\), since \(M_2\) accepts everything).

4.14. Intersection of Complex FSAs (Tutorial 4, Example 6)

Given two FSAs over alphabet \(\{a, b\}\):

\(M_1\):

• States: \(q_0\) (start), \(q_1\), \(q_2\) (accepting), \(q_3\)
• Transitions: \(q_0 \xrightarrow{a} q_0\), \(q_0 \xrightarrow{b} q_1\); \(q_1 \xrightarrow{a} q_2\), \(q_1 \xrightarrow{b} q_3\); \(q_2\) loops on \(a,b\); \(q_3\) loops on \(a,b\)

\(M_2\):

• States: \(p_0\) (start), \(p_1\), \(p_2\) (accepting)
• Transitions: \(p_0 \xrightarrow{a} p_1\), \(p_0 \xrightarrow{b} p_0\); \(p_1 \xrightarrow{a} p_2\), \(p_1 \xrightarrow{b} p_0\); \(p_2\) loops on \(a,b\)

Construct \(M_1 \cap M_2\) and simplify by removing unreachable states.

Click to see the solution

Key Concept: Use product construction, then identify and remove unreachable states.

1. Build the full product automaton:

   • States: \(Q_1 \times Q_2 = \{q_0, q_1, q_2, q_3\} \times \{p_0, p_1, p_2\} = 12\) states total
   • Initial state: \((q_0, p_0)\)
   • Accepting states: \(\{(q, p) : q \in \{q_2\} \land p \in \{p_2\}\} = \{(q_2, p_2)\}\)

2. Determine transitions for all pairs: For example:

   • From \((q_0, p_0)\) on ‘a’: \((\delta_1(q_0, a), \delta_2(p_0, a)) = (q_0, p_1)\)
   • From \((q_0, p_0)\) on ‘b’: \((q_1, p_0)\)
   • From \((q_1, p_1)\) on ‘a’: \((q_2, p_2)\) — this leads to the accepting state!

3. Identify reachable states from \((q_0, p_0)\):

   To reach \(q_2\) in \(M_1\): must go \(q_0 \xrightarrow{b} q_1 \xrightarrow{a} q_2\) To reach \(p_2\) in \(M_2\): must go \(p_0 \xrightarrow{a} p_1 \xrightarrow{a} p_2\) (and \(p_2\) loops on all symbols)

   Path for “aaba”: \((q_0, p_0) \xrightarrow{a} (q_0, p_1) \xrightarrow{a} (q_0, p_2) \xrightarrow{b} (q_1, p_2) \xrightarrow{a} (q_2, p_2)\) ✓

4. Simplified automaton (after removing unreachable states):

Answer: The simplified intersection FSA accepts strings that reach both \(q_2\) in \(M_1\) and \(p_2\) in \(M_2\). A minimal accepting string is “aaba”.

4.15. Union of Two FSAs (Tutorial 4, Example 7)

Using the same \(M_1\) and \(M_2\) from Example 5 (odd-length strings and all strings), construct \(M_1 \cup M_2\).

Click to see the solution

Key Concept: Use product construction with accepting states being pairs where at least one component is accepting.

1. Product states and transitions are the same as for intersection:

   • \(Q = \{(q_0, p_0), (q_1, p_0)\}\)
   • Initial: \((q_0, p_0)\)
   • Transitions:
     • \((q_0, p_0) \xrightarrow{a} (q_1, p_0)\)
     • \((q_1, p_0) \xrightarrow{a} (q_0, p_0)\)

2. Determine accepting states (at least one component accepting): \(F = \{(q, p) : q \in F_1 \lor p \in F_2\}\)

   Since \(F_2 = \{p_0\}\) and all reachable states have \(p = p_0\), we have \(p \in F_2\) for all states.

   Therefore: \(F = \{(q_0, p_0), (q_1, p_0)\}\) (both states are accepting)

3. Result: Since the initial state \((q_0, p_0)\) is accepting, even the empty string \(\epsilon\) is accepted. In fact, every string is accepted.

Answer: \(M_1 \cup M_2\) accepts all strings over \(\{a\}\) (same as \(M_2\), since \(M_2 \subseteq M_1 \cup M_2\) and \(M_2 = \Sigma^*\)).

4.16. Difference of Two FSAs (Tutorial 4, Example 8)

Compute \(M_1 \setminus M_2\) where \(M_1\) accepts odd-length strings and \(M_2\) accepts all strings (from previous examples).

Click to see the solution

Key Concept: Accepting states are pairs where the first component is accepting and the second is NOT accepting.

1. Product construction (same states and transitions as before):
   • \(Q = \{(q_0, p_0), (q_1, p_0)\}\)
   • Initial: \((q_0, p_0)\)
2. Determine accepting states: \(F = \{(q, p) : q \in F_1 \land p \notin F_2\}\)
   • \(F_1 = \{q_1\}\)
   • \(F_2 = \{p_0\}\)
   • For \((q_1, p_0)\): \(q_1 \in F_1\) ✓ but \(p_0 \in F_2\) ✗ (we need \(p_0 \notin F_2\))
   • For \((q_0, p_0)\): \(q_0 \notin F_1\) ✗
   • Result: \(F = \emptyset\) (no accepting states)

Answer: \(M_1 \setminus M_2 = \emptyset\) because every string in \(M_1\) is also in \(M_2\) (since \(M_2\) accepts everything).

4.17. Difference of Two FSAs (Tutorial 4, Example 9)

Compute \(M_2 \setminus M_1\) (all strings minus odd-length strings).

Click to see the solution

1. Accepting states: \(F = \{(q, p) : q \in F_2 \land p \notin F_1\}\)
   • We need: \(p \in \{p_0\}\) AND \(q \notin \{q_1\}\)
   • For \((q_0, p_0)\): \(p_0 \in F_2\) ✓ and \(q_0 \notin F_1\) ✓ → accepting
   • For \((q_1, p_0)\): \(p_0 \in F_2\) ✓ but \(q_1 \in F_1\) ✗ → not accepting
   • Result: \(F = \{(q_0, p_0)\}\)

Answer: \(M_2 \setminus M_1\) accepts even-length strings (including \(\epsilon\)).